{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Equal Sum of Two Arrays After Replacing Zeros"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数组的最小相等和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个由正整数和 <code>0</code> 组成的数组 <code>nums1</code> 和 <code>nums2</code> 。</p>\n",
    "\n",
    "<p>你必须将两个数组中的<strong> 所有</strong> <code>0</code> 替换为 <strong>严格</strong> 正整数，并且满足两个数组中所有元素的和 <strong>相等</strong> 。</p>\n",
    "\n",
    "<p>返回 <strong>最小</strong> 相等和 ，如果无法使两数组相等，则返回 <code>-1</code><em> </em>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums1 = [3,2,0,1,0], nums2 = [6,5,0]\n",
    "<strong>输出：</strong>12\n",
    "<strong>解释：</strong>可以按下述方式替换数组中的 0 ：\n",
    "- 用 2 和 4 替换 nums1 中的两个 0 。得到 nums1 = [3,2,2,1,4] 。\n",
    "- 用 1 替换 nums2 中的一个 0 。得到 nums2 = [6,5,1] 。\n",
    "两个数组的元素和相等，都等于 12 。可以证明这是可以获得的最小相等和。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums1 = [2,0,2,0], nums2 = [1,4]\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>无法使两个数组的和相等。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums1.length, nums2.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums1[i], nums2[i] &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-equal-sum-of-two-arrays-after-replacing-zeros](https://leetcode.cn/problems/minimum-equal-sum-of-two-arrays-after-replacing-zeros/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-equal-sum-of-two-arrays-after-replacing-zeros](https://leetcode.cn/problems/minimum-equal-sum-of-two-arrays-after-replacing-zeros/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,2,0,1,0]\\n[6,5,0]', '[2,0,2,0]\\n[1,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        if nums1 is None or len(nums1) == 0 or nums2 is None or len(nums2) == 0:\n",
    "            return -1\n",
    "        \n",
    "        cnt_zero_nums1, cnt_zero_nums2 = 0, 0\n",
    "        for num in nums1:\n",
    "            if num == 0:\n",
    "                cnt_zero_nums1 += 1\n",
    "        \n",
    "        for num in nums2:\n",
    "            if num == 0:\n",
    "                cnt_zero_nums2 += 1\n",
    "            \n",
    "        sum_nums1, sum_nums2 = sum(nums1), sum(nums2)\n",
    "\n",
    "        if sum_nums1 < sum_nums2:\n",
    "            return max(sum_nums1 + cnt_zero_nums1, sum_nums2 + cnt_zero_nums2) if (sum_nums1 + cnt_zero_nums1 <= sum_nums2 + cnt_zero_nums2 and cnt_zero_nums1 != 0) or (sum_nums1 + cnt_zero_nums1 > sum_nums2 + cnt_zero_nums2 and cnt_zero_nums2 != 0) else -1\n",
    "        elif sum_nums1 > sum_nums2:\n",
    "            return max(sum_nums1 + cnt_zero_nums1, sum_nums2 + cnt_zero_nums2) if sum_nums1 + cnt_zero_nums1 >= sum_nums2 + cnt_zero_nums2 and cnt_zero_nums2 != 0 or sum_nums1 + cnt_zero_nums1 < sum_nums2 + cnt_zero_nums2 and cnt_zero_nums1 != 0 else -1\n",
    "        else:\n",
    "            return max(sum_nums1 + cnt_zero_nums1, sum_nums2 + cnt_zero_nums2) if cnt_zero_nums1 == 0 and cnt_zero_nums2 == 0 or cnt_zero_nums1 != 0 and cnt_zero_nums2 != 0 else -1\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 时间复杂度O(n)\n",
    "# 空间复杂度O(1) 仅用了若干变量\n",
    "class Solution:\n",
    "    def minSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        i,j,i_,j_ = sum(nums1),sum(nums2),0,0\n",
    "        for k in range(0,len(nums1)):\n",
    "            if nums1[k] == 0:\n",
    "                i_+=1 # 先统计第一个数组0的个数\n",
    "        for k in range(0,len(nums2)):\n",
    "            if nums2[k] == 0:\n",
    "                j_+=1 # 然后是第二个数组0的个数\n",
    "        if i == j and i_ == 0 and j_ == 0:\n",
    "            return i # 如果值相等 第一个数组和第二个数组都没0 则返回任意一个数组的和\n",
    "        if i_ == 0 and j_ == 0:\n",
    "            return -1 if i != j else i # 如果第一个和第二个都没0 则判断一下他们的和\n",
    "        if i_ == 0 and j_ != 0:\n",
    "            return -1 if j >= i or (i-j)//j_ == 0 else i # 第一个数组有0 第二个数组没0 代入公式求解即可\n",
    "        if i_ != 0 and j_ == 0:\n",
    "            return -1 if i >= j or (j-i)//i_ == 0 else j # 第一个数组没0 第二个数组有0 代入公式求解即可\n",
    "        o = 10 ** 11 # 初始化一个无穷大的答案\n",
    "        for k in range(0,len(nums1)):\n",
    "            if nums1[k] == 0: \n",
    "                nums1[k] = 1 # 假设把第一个数组的0全部改成1\n",
    "        k_ = sum(nums1) # 更新现在的值       \n",
    "        o = min(o,o if j >= k_ or (k_-j)//j_ == 0 else k_) # 代入公式求解 这里不满足不要返回-1 而是原来的o\n",
    "        for k in range(0,len(nums2)):\n",
    "            if nums2[k] == 0:\n",
    "                nums2[k] = 1 # 假设把第二个数组的0改成1\n",
    "        k_ = sum(nums2) # 更新现在的和\n",
    "        o = min(o,o if i >= k_ or (k_-i)//i_ == 0 else k_) # 代入公式求解 这里不满足不要返回-1 而是原来的o\n",
    "        return o # 返回答案"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        a = nums1.count(0)\n",
    "        b = nums2.count(0)\n",
    "        \n",
    "        if a:\n",
    "            if b:\n",
    "                return max(a + sum(nums1), b + sum(nums2))\n",
    "        \n",
    "            if a + sum(nums1) > sum(nums2):\n",
    "                return -1\n",
    "            \n",
    "            return sum(nums2)\n",
    "        if b:\n",
    "            if b + sum(nums2) > sum(nums1):\n",
    "                return -1\n",
    "            return sum(nums1)\n",
    "        return -1 if sum(nums1) != sum(nums2) else sum(nums1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left, bisect_right, insort_left, insort_right, insort, bisect\n",
    "from math import ceil, floor, pow, gcd, sqrt, log10, fabs, fmod, factorial, inf, pi, e\n",
    "from heapq import heapify, heapreplace, heappush, heappop, heappushpop, nlargest, nsmallest\n",
    "from collections import defaultdict, Counter, deque\n",
    "from itertools import permutations, combinations, combinations_with_replacement, accumulate, count, groupby, pairwise\n",
    "from queue import PriorityQueue, Queue, LifoQueue\n",
    "from functools import lru_cache, cache, reduce\n",
    "from typing import List, Optional\n",
    "import sys\n",
    "\n",
    "from sortedcontainers import SortedList, SortedDict, SortedSet\n",
    "\n",
    "sys.setrecursionlimit(10001000)\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "INF = int(1e20)\n",
    "INFMIN = float('-inf')  # 负无穷\n",
    "INFMAX = float('inf')  # 正无穷\n",
    "PI = 3.141592653589793\n",
    "direc = [(1, 0), (0, 1), (-1, 0), (0, -1)]\n",
    "direc8 = [(1, 0), (0, 1), (-1, 0), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]\n",
    "ALPS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'\n",
    "alps = 'abcdefghijklmnopqrstuvwxyz'\n",
    "\n",
    "'''\n",
    "gcd(), ord(), chr(), lower(), upper() 最大公约数/ASCII字符数值/数值ASCII字符/小写/大写\n",
    "startswith(s), endswith(s), find(), index(), count(s)  字符串是否以s开始的/字符串是否以s结尾的/查找返回的是索引/获取索引\n",
    "isalpha(), isdigit(), space(),join()  判断是否全为字符/判断是否全为数字/判断是否为空格/拼接\n",
    "eval() 字符串转换成列表、元组或者字典/\n",
    "uniform(x, y), pow(x, y)# 随机生成下一个实数，它在[x,y]范围内/ x**y 运算后的值。\n",
    "字典推倒式 {key: len(key) for key in list}\n",
    "列表推倒式 [i for i in range(100) if i % 3 == 0] 可切片,可索引,可重复\n",
    "集合推倒式 {i ** 2 for i in (1, 2, 3)}  不可索引,不可切片,不可重复元素\n",
    "'''\n",
    "\n",
    "# 数值和字母进行转换 ord()函数是把字符转换成ASCII码 chr()函数是把ASCII码转换成字符\n",
    "def alp(i):\n",
    "    return chr(ord('a') + i % 26)  # i=0->'a', i=25->'z'\n",
    "\n",
    "# lcm 最小公倍数 gcd 最大公约数\n",
    "def lcm(x, y):\n",
    "    return x * y // gcd(x, y)\n",
    "\n",
    "# 快速幂\n",
    "def qpow(x, y):\n",
    "    ans = 1\n",
    "    while y:\n",
    "        if y & 1:\n",
    "            ans *= x\n",
    "        x *= x\n",
    "        y >>= 1\n",
    "    return ans\n",
    "\n",
    "# 求组合数\n",
    "def Comb(n, m, p):\n",
    "    a = (factorial(n)) % p\n",
    "    b = (qpow(factorial(m), (p - 2), p)) % p\n",
    "    c = (qpow(factorial(n - m), (p - 2), p)) % p\n",
    "    return a * b * c % p\n",
    "\n",
    "# lucas求组合数\n",
    "def Lucas(n, m, p):\n",
    "    if m == 0:\n",
    "        return 1\n",
    "    return Comb(n % p, m % p, p) * Lucas(n // p, m // p, p) % p\n",
    "\n",
    "def rep():\n",
    "    a = list(map(int, input().split()))\n",
    "    return a\n",
    "\n",
    "def sep():\n",
    "    a = input().rstrip('\\n')\n",
    "    return a\n",
    "\n",
    "# --idea \n",
    "# -*- coding: utf-8 -*-\n",
    "# @Author  : hakusai\n",
    "# @Time    : 2023/11/26 17:00\n",
    "\n",
    "class Solution:\n",
    "    def minSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        s1 = sum(max(x, 1) for x in nums1)\n",
    "        s2 = sum(max(x, 1) for x in nums2)\n",
    "        if s1 < s2 and 0 not in nums1 or s2 < s1 and 0 not in nums2:\n",
    "            return -1\n",
    "        return max(s1, s2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        s1 = sum(max(x,1) for x in nums1)\n",
    "        s2 = sum(max(x,1) for x in nums2)\n",
    "        if s1 < s2 and 0 not in nums1 or s2 < s1 and 0 not in nums2:\n",
    "            return -1\n",
    "        return max(s1, s2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        zero_index_1 = [i for i in range(len(nums1)) if nums1[i] == 0]\n",
    "        zero_index_2 = [i for i in range(len(nums2)) if nums2[i] == 0]\n",
    "        sum_1 = sum(nums1) + len(zero_index_1)\n",
    "        sum_2 = sum(nums2) + len(zero_index_2)\n",
    "        if len(zero_index_1) == 0 and \\\n",
    "            sum_2 > sum_1:\n",
    "                return -1\n",
    "        if len(zero_index_2) == 0 and \\\n",
    "            sum_1 > sum_2:\n",
    "                return -1\n",
    "\n",
    "        for i in zero_index_1:\n",
    "            nums1[i] = 1\n",
    "        for i in zero_index_2:\n",
    "            nums2[i] = 1\n",
    "\n",
    "        if sum_1 > sum_2:\n",
    "            diff = sum_1 - sum_2\n",
    "            divisor = diff // len(zero_index_2)\n",
    "            remainder = diff % len(zero_index_2)\n",
    "            for i in zero_index_2:\n",
    "                nums2[i] += divisor\n",
    "            for i in range(remainder):\n",
    "                nums2[i] += 1\n",
    "        if sum_1 < sum_2:\n",
    "            diff = sum_2 - sum_1\n",
    "            divisor = diff // len(zero_index_1)\n",
    "            remainder = diff % len(zero_index_1)\n",
    "            for i in zero_index_1:\n",
    "                nums1[i] += divisor\n",
    "            for i in range(remainder):\n",
    "                nums1[i] += 1\n",
    "        return sum(nums1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        count1 = Counter(nums1)[0]\n",
    "        count2 = Counter(nums2)[0]\n",
    "        sum1 = sum(nums1)\n",
    "        sum2 = sum(nums2)\n",
    "        if count1 == 0 and count2 == 0:\n",
    "            if sum1 == sum2:\n",
    "                return sum1\n",
    "            else:\n",
    "                return -1\n",
    "        if sum2+count2 > sum1 and count1 == 0:\n",
    "            return -1\n",
    "        if sum1+count1 > sum2 and count2 == 0:\n",
    "            return -1\n",
    "        return max(sum1+count1, sum2+count2)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSum(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        cnt1 = Counter(nums1)\n",
    "        cnt2 = Counter(nums2)\n",
    "\n",
    "        sum1,sum2 = sum(nums1),sum(nums2)\n",
    "\n",
    "        cnt1_0 = cnt1[0]\n",
    "        cnt2_0 = cnt2[0]\n",
    "\n",
    "        if cnt1_0 != 0 and cnt2_0 != 0:\n",
    "            return max(sum1 + cnt1_0,sum2 + cnt2_0)\n",
    "        elif cnt1_0 == 0 and cnt2_0 == 0:\n",
    "            return sum1 if sum1 == sum2 else -1\n",
    "        else:\n",
    "            if cnt1_0 != 0:\n",
    "                if sum1 < sum2 and sum2 - sum1 >= cnt1_0:\n",
    "                    return max(sum1 + cnt1_0,sum2)\n",
    "                else:\n",
    "                    return -1\n",
    "            elif cnt2_0 != 0:\n",
    "                if sum1 > sum2 and sum1 - sum2 >= cnt2_0:\n",
    "                    return max(sum1,sum2 + cnt2_0)\n",
    "                else:\n",
    "                    return -1\n",
    "            else:\n",
    "                return -1\n",
    "\n",
    "\n",
    "        \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
